﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    class Problem124b : IProblem
    {
        public string Calculate()
        {
            int target = 10000;
            int limit = 100000;

            long[] sorted = new long[limit];
            long[] rad = new long[limit + 1];

            sorted[0] = 1;
            rad[1] = 1;

            SieveOfAtkin sieve = new SieveOfAtkin(limit);
            List<int> p = new List<int>();
            p.Add(2);
            for (int j = 3; j <= limit; j += 2)
                if (sieve.IsPrime(j))
                    p.Add(j);

            int i = 1;
            for (long n = 2; n <= limit; n++)
            {
                if (rad[n] != 0)
                    continue;

                if (sieve.IsPrime(n))
                {
                    long tempN = n;
                    while (tempN <= limit)
                    {
                        rad[tempN] = n;
                        sorted[i] = tempN;
                        i++;
                        tempN *= n;
                    }
                }
                else
                {
                    long tempN = n;
                    long product = 1;
                    List<long> radicals = new List<long>();

                    //nabavi radikale
                    for (int j = 0; j < p.Count && tempN > 1; j++)
                    {
                        if (sieve.IsPrime(tempN))
                        {
                            radicals.Add(tempN);
                            product *= tempN;
                            break;
                        }

                        if (tempN % p[j] == 0)
                        {
                            radicals.Add(p[j]);
                            product *= p[j];
                            while (tempN > 1 && tempN % p[j] == 0)
                                tempN /= p[j];
                        }
                    }

                    int[] usage = new int[radicals.Count];
                    for (int j = 0; j < usage.Length; j++)
                        usage[j] = 1;

                    int k = usage.Length - 1;
                    usage[k] = 0;

                    List<long> unsorted = new List<long>();

                    while (true)
                    {
                        usage[k]++;
                        tempN = 1;
                        for (int j = 0; j < usage.Length && tempN <= limit; j++)
                            tempN *= (long)Math.Pow(radicals[j], usage[j]);

                        if (tempN <= limit)
                        {
                            k = usage.Length - 1;
                            rad[tempN] = product;
                            unsorted.Add(tempN);
                        }
                        else if (k == 0)
                            break;
                        else
                        {
                            usage[k] = 1;
                            k--;
                        }
                    }

                    var tempSort = unsorted.OrderBy(x => x);
                    foreach (long l in tempSort)
                    {
                        sorted[i] = l;
                        i++;
                    }
                }
            }

            return sorted[target - 1].ToString();
        }
    }
}
